﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_69_MySqrt
{
    class MainProject
    {
        //解体思路：二分查找，原本的二分查找是有固定数组，是可以查询不到，和这里有区别
        //
        static void Main(string[] args)
        {

            //Console.WriteLine(IsPalindrome(0));
            Console.WriteLine(MySqrt1(2147483647));
            Console.WriteLine(int.MaxValue);
            Console.ReadKey();
        }


        /// <summary>
        /// 1.袖珍计算机方法(时间O(1),空间O(1))
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public static int MySqrt1(int x)
        {
            if (x==0)
            {
                return 0;
            }
            long value = (int)Math.Exp(0.5f * Math.Log(x));
            return (int)(((value + 1) * (value + 1)) <= x ? (value + 1) : value);
        }

        /// <summary>
        /// 二分查找法 时间复杂度：O(logN)  空间复杂度 O(1)
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public static int MySqrt2(int x)
        {
            long low = 1;
            long high = x;
            long middle = 0;
            while (low<=high)//这里动态修改low和high的值  限定条件
            {
                middle = (low + high) / 2;
                if (middle * middle < x)
                {
                    low = middle+1; //低的+1
                }
                else if (middle * middle > x)
                {
                    high = middle-1;  //高的-1
                }
                else
                {
                    return (int)middle;
                }
            }
            return (int)(low-1);
        }

        /// <summary>
        /// 牛顿迭代法(是一种快速求解函数零点的方法)
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        //public static int MySqrt3(int x)
        //{
            
        //}
    }
}
